package Algorithm.DoublePointer;

import java.util.*;

//https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
public class Leetcode239 {
    //自己的
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums==null||nums.length==0||k==0)
                return new int[0];
            List<Integer> list = new ArrayList<Integer>();

            int left = 0;
            int right = k-1;

            int maxPoint = searchMax(nums, left, right);
            int max = nums[maxPoint];
            list.add(max);

            while(right<nums.length-1){
                if(nums[right+1]>=max){
                    maxPoint = right;
                    max = nums[right+1];
                }else if(maxPoint == left){
                    maxPoint = searchMax(nums,left+1,right+1);
                    max = nums[maxPoint];

                }

                list.add(max);
                left++;
                right++;
            }

            int[] result = new int[list.size()];
            for(int i=0;i<result.length;i++){
                result[i] = list.get(i);
            }

            return result;

        }

        public int searchMax(int nums[], int left, int right){
            int start = left;
            int r = left;

            while(start<=right){
                if(nums[start] >= nums[r]){
                    r = start;
                }
                start ++;
            }

            return r;


        }
    }

    //优先队列
    class Solution2 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0)
                return new int[0];


            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
                public int compare(int[] pair1, int[] pair2){
                    return pair1[0]!=pair2[0]?pair2[0]-pair1[0]:pair2[1]-pair1[1];
                }
            });

            for(int i=0;i<k;i++){
                pq.offer(new int[]{nums[i],i});
            }

            System.out.println(pq.peek()[0]);

            int n = nums.length;
            int[] ans = new int[n-k+1];
            ans[0] = pq.peek()[0];

            for(int i=k;i<n;i++){
                pq.offer(new int[]{nums[i],i});

                while(pq.peek()[1]<=i-k){
                    pq.poll();
                }
                ans[i-k+1] = pq.peek()[0];

            }
            return ans;
        }
    }

    //单调栈
    class Solution3 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0)
                return new int[0];

            int n = nums.length;
            Deque<Integer> deque = new LinkedList<Integer>();

            for(int i=0;i<k;i++){
                while(!deque.isEmpty()&&nums[deque.peekLast()]<=nums[i]){
                    deque.pollLast();
                }
                deque.offerLast(i);
            }

            int[] ans = new int[n - k + 1];
            ans[0] = nums[deque.peekFirst()];

            for(int i=k;i<n;i++){
                while(!deque.isEmpty()&&nums[deque.peekLast()]<=nums[i]){
                    deque.pollLast();
                }
                deque.offerLast(i);

                while(deque.peekFirst()<=i-k){
                    deque.pollFirst();
                }

                ans[i -k + 1] = nums[deque.peekFirst()];


            }

            return ans;
        }


    }


}
